#if 0
#include<iostream>
using namespace std;
#include<stack>
#include<vector>
#include<unordered_map>


struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* Reverse(ListNode* head)
    {
        ListNode* cur = head, * prev = nullptr;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = Reverse(l1);
        l2 = Reverse(l2);
        ListNode* head = new ListNode;
        ListNode* tail = head;
        int next = 0;
        while (l1 && l2)
        {
            int tmp = l1->val + l2->val + next;
            next = tmp / 10;
            tmp %= 10;
            ListNode* node = new ListNode(tmp);
            tail->next = node;
            tail = node;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (next)
        {
            ListNode* node = new ListNode(next % 10);
            tail->next = node;
            tail = node;
            next /= 10;
        }
        return head->next;
    }

    void reorderList(ListNode* head) {
        if (!head) return;
        stack<ListNode*> st;
        ListNode* cur = head;
        while (cur)
        {
            st.push(cur);
            cur = cur->next;
        }
        cur = head;
        ListNode* cur2 = st.top(), * n1, * n2;
        st.pop();
        while (cur != cur2 && cur->next != cur2)
        {
            n1 = cur->next;
            n2 = cur2->next;
            cur->next = cur2;
            cur2->next = n1;
            cur = n1;
            cur2 = st.top();
            st.pop();
        }
        cur2->next = nullptr;
    }
};

ListNode* Create(int* a, int n)
{
    ListNode* head = new ListNode;
    ListNode* tail = head;
    for (int i = 0; i < n; ++i)
    {
        tail->next = new ListNode(a[i]);
        tail = tail->next;
    }
    tail = head->next;
    delete head;
    return tail;
}
int main()
{
    //int a1[] = { 9,9,9,9,9,9,9 };
    //int a2[] = { 9,9,9,9 };
    //ListNode* l1 = Create(a1, sizeof(a1) / sizeof(int));
    //ListNode* l2 = Create(a2, sizeof(a2) / sizeof(int));
    //ListNode* ans = Solution().addTwoNumbers(l1, l2);

    int a1[] = { 1,2,3,4 };
    ListNode* l1 = Create(a1, sizeof(a1) / sizeof(int));
    Solution().reorderList(l1);
	return 0;
}

class Solution {
public:
    bool containsDuplicate(const vector<int>& nums) {
        unordered_map<int, int> hash;
        for (auto& e : nums)
        {
            if (hash[e] != 0)
                return false;
            ++hash[e];
        }
        return true;
    }
};

int main()
{
    bool ret = Solution().containsDuplicate({ 1,2,3,1 });
    cout << ret << endl;
    return 0;
}
#endif
